package ink.lovejinhu.interview;

import ink.lovejinhu.common.ListNode;

/**
 * @Author: jin
 * @Date: 2021/9/2 20:54
 * @Version: V1.0
 * @Slogan: Great people are not born great, but show their greatness in the process of growing up
 **/
public class Hw04 {
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = null;
        Hw04 hw04 = new Hw04();
        ListNode listNode = hw04.deleteN(listNode1, 1);
        while (listNode != null) {

            System.out.print(listNode.val);
            listNode = listNode.next;
        }
    }

    /**
     * 双指针
     *
     * @param listNode
     * @return
     */
    public ListNode deleteN(ListNode listNode, int n) {
        ListNode temp = listNode;   //保留头
        /**
         * 找一个n长度的尺子
         */
        //让v0先走n次，然后v0和v1一起走，v0走到末尾，v1走到的就是倒数第n个，删除
        ListNode v0 = temp;
        ListNode v1 = temp;
        for (int i = 0; i < n; i++) {
            if (v0 == null) {
                return null;
            }
            v0 = v0.next;
        }
        ListNode pre = null;   //保留前驱
        while (v0 != null) {
            v0 = v0.next;
            pre = v1;
            v1 = v1.next;
        }
        //v1走到的就是倒数第n个
        pre.next = v1.next; //前驱的后继直接直线倒数第n个节点
        v1.next = null;  //将之前的后继删除
        return temp;
    }
}
